home *** CD-ROM | disk | FTP | other *** search
/ MacTech 1 to 12 / MacTech-vol-1-12.toast / Source / MacTech® Magazine / Volume 12 - 1996 / 12.07 Jul 96 / EdgeDetector.c < prev    next >
Encoding:
Text File  |  1996-05-08  |  10.7 KB  |  453 lines  |  [TEXT/R*ch]
  1. /*
  2.   23 April 1996.
  3.   Submission to MacTech Programmer's challenge for May-96.
  4.   Copyright 1996, Ernst Munter, Kanata, ON, Canada.
  5.  
  6.         "Edge Detector"
  7.  
  8. Version 3: Uses GetPixBaseAddr() in line 209.
  9.  
  10. Problem Statement
  11. -----------------
  12. Given a Pixmap image, create a Bitmap which shows the edges
  13. in the image.
  14.  
  15. Pixmaps may have 8, 16, or 32 bit colors. Parameters control
  16. which colors should contribute to the edge detection, and a
  17. threshold for the color space difference (an RMS value) to
  18. be considered an edge.
  19.  
  20. All 16 bits of the individual color values must be
  21. considered, which can result in 32-bit overflow when squares
  22. are added.
  23.  
  24. Solution
  25. --------
  26. The general idea is to process 2-row strips of the image
  27. through an intermediate ColorSpec stage in which the
  28. "value" fields are used to mark edge pixels. 
  29.  
  30. Step1:
  31.  
  32. We allocate a small amount of memory, sufficient to hold
  33. two rows of pixels in ColorSpec format (8 bytes per pixel).
  34. Pixels from each row in the Pixmap are converted to
  35. ColorSpec format (RGB + "value").
  36.  
  37. Step2:
  38.  
  39. The two lines are scanned with 4 different patterns
  40. to determine edges:  given 2 rows with pixels as shown
  41.  
  42.     A B C D E F G H ...
  43.     a b c d e f g h ...
  44.  
  45. We compare pixel pairs in four separate runs of EdgePairs():
  46.     a-b, b-c, c-d, d-e ...  (WEST - EAST)
  47.     A-b, B-c, C-d, D-e ...  (NORTH-WEST - SOUTH-EAST)
  48.     B-a, C-b, D-c, E-d ...  (NORTH-EAST - SOUTH-WEST)
  49.     A-a, B-b, C-c, D-d ...  (NORTH - SOUTH)
  50.  
  51. This procedure is repeated for rows 0 and 1, then 1 and 2,
  52. 2 and 3, and so on.  (Plus an West-East run for row 0).
  53.  
  54. During each run, the "value" field of every pair of pixels
  55. found to be part of an edge is set to -1 (0xFFFF).
  56. All other values remain at 0.
  57.  
  58. Step 3:
  59.  
  60. Before shifting down to the next row, the ColorSpecs
  61. of the upper row are scanned to construct a row of
  62. the Bitmap.
  63.  
  64. Optimizations
  65. -------------
  66. The combinations of pixel size and edge types are dealt
  67. with as follows:
  68.  
  69. All pixel types are normalized to a single ColorSpec format
  70. by the GetLine procedure.
  71.  
  72. Different edge types call for different series of tests.
  73. Specifically, 1, 2, or 3 colors can be optimized separately.
  74. On of a set of 7 separate short functions is selected at
  75. runtime.  This requires the edge type to be evaluated only
  76. once, to select the EdgeXXX procedure that will be used many
  77. times as the image is scanned from top to bottom.
  78.  
  79. Comparing an RMS (root of sum of squares) value with a
  80. threshold is equivalent to comparing the sum of squares
  81. with the square of the threshold value.  This avoids the
  82. need to compute square roots.
  83.  
  84. In the case of a single color edge type, the square of the
  85. difference would not need to be formed.  A simple comparison
  86. of the threshold with the absolute difference would suffice.
  87. However, the runtime difference between a multiply and
  88. computing the absolute value would depend on CPU type etc,
  89. and would tend to be small.  I opted for uniformity, and
  90. square all differences.
  91.  
  92. The dynamically allocated storage should typically fit
  93. inside the CPU cache, and not slow things down as it is
  94. read and written continuously.
  95.  
  96. Assumptions
  97. -----------
  98. Bitmap is large enough to hold the result.
  99. eType is within the range of redOnly to redGreenAndBlue,
  100. otherwise the call will certainly crash.
  101.  
  102. Amount of static memory = 8 pointers (32 bytes)
  103. Amount of dynamic memory required is for 2 rows of
  104. ColorSpec records (a 1024 pix wide image -> 16K of storage).
  105.  
  106. */
  107.  
  108.  
  109.  
  110. /********************** HEADER INFO **********************/
  111. // Please use what you need in your environment.
  112.  
  113. #include "edge.h"
  114. // Contains PixMap, BitMap and EdgeType defs
  115.  
  116. #include <stdlib.h>
  117. /*************** END OF DISPOSABLE HEADER INFO ************/
  118.  
  119.  
  120. /******************* Definitions **************************/
  121.  
  122. typedef void EdgeProc(
  123.     ColorSpec*     P,
  124.     ColorSpec*     Q,
  125.     int         size,
  126.     unsigned long     TH);
  127.  
  128. /******************* Function Prototypes ******************/
  129. void EdgeDetect(
  130.     PixMapHandle     pMapH,
  131.     BitMap         *bMap,
  132.     unsigned short     threshold,
  133.     EdgeType     eType);
  134.  
  135. void Get1Line(
  136.     ColorSpec*     line,
  137.     void*         pix,
  138.     int         size,
  139.     ColorSpec*     CT,
  140.     int         pixelSize);
  141.  
  142. void EdgeRed(
  143.     ColorSpec*     P,
  144.     ColorSpec*     Q,
  145.     int         size,
  146.     unsigned long     TH);
  147.  
  148. void EdgeGreen(
  149.     ColorSpec*     P,
  150.     ColorSpec*     Q,
  151.     int         size,
  152.     unsigned long     TH);
  153.  
  154. void EdgeRedGreen(
  155.     ColorSpec*     P,
  156.     ColorSpec*     Q,
  157.     int         size,
  158.     unsigned long     TH);
  159.  
  160. void EdgeBlue(
  161.     ColorSpec*     P,
  162.     ColorSpec*     Q,
  163.     int         size,
  164.     unsigned long     TH);
  165.  
  166. void EdgeRedBlue(
  167.     ColorSpec*     P,
  168.     ColorSpec*     Q,
  169.     int         size,
  170.     unsigned long     TH);
  171.  
  172. void EdgeGreenBlue(
  173.     ColorSpec*     P,
  174.     ColorSpec*     Q,
  175.     int         size,
  176.     unsigned long     TH);
  177.  
  178. void EdgeRedGreenBlue(
  179.     ColorSpec*     P,
  180.     ColorSpec*     Q,
  181.     int         size,
  182.     unsigned long     TH);
  183.  
  184. void Copy2Bitmap(
  185.     ColorSpec*     P,
  186.     unsigned char*     bits,
  187.     int         size);
  188.  
  189. /********************* Static Allocations *****************/
  190.  
  191. static EdgeProc* EdgeProcedure[8] = {
  192.     0,
  193.     EdgeRed,
  194.     EdgeGreen,
  195.     EdgeRedGreen,
  196.     EdgeBlue,
  197.     EdgeRedBlue,
  198.     EdgeGreenBlue,
  199.     EdgeRedGreenBlue};
  200.  
  201. /********************* The EdgeDetect Function ************/
  202. void EdgeDetect(
  203.     PixMapHandle     pMapH,
  204.     BitMap         *bMap,
  205.     unsigned short     threshold,
  206.     EdgeType     eType) {
  207. PixMap*     pm=*pMapH;
  208. //unsigned char*     pix=(unsigned char*)pm->baseAddr;
  209. unsigned char*     pix=(unsigned char*)GetPixBaseAddr(pMapH);
  210. unsigned char*     bits=(unsigned char*)bMap->baseAddr;
  211. unsigned long     TH=(unsigned long)threshold*threshold;
  212. int         y;
  213. int         pixelSize=pm->pixelSize;
  214. int         pixRowBytes=pm->rowBytes & 0x3FFF;
  215. int         pixInRow=pm->bounds.right-pm->bounds.left;
  216. int         bitRowBytes=bMap->rowBytes;
  217.  
  218. ColorSpec*     allocated;
  219. ColorSpec*     line0;
  220. ColorSpec*     line1;
  221. ColorSpec*     CTable=(*(pm->pmTable))->ctTable;
  222. EdgeProc*    EP;
  223.  
  224. // Get memory for a 2-row strip of pixels:
  225.   if (0==(allocated=(ColorSpec*)malloc(
  226.     2*sizeof(ColorSpec)*pixInRow))) return;
  227.   line0=allocated-1;  //(we always use pre-increment later)
  228.   line1=line0+pixInRow;
  229.  
  230. // Determine EdgeProc to use:
  231.   EP=EdgeProcedure[eType];
  232.  
  233. // Prepare first row:
  234.   Get1Line(line0,pix,pixInRow,CTable,pixelSize);
  235.   (*EP)(line0,line0+1,pixInRow-1,TH);    //W--E
  236.  
  237. // Process remaining rows:
  238.   for (y=pm->bounds.top+1;y<pm->bounds.bottom;y++) {
  239.     pix+=pixRowBytes;
  240.     Get1Line(line1,pix,pixInRow,CTable,pixelSize);
  241.                                                              
  242.     (*EP)(line1,  line1+1,pixInRow-1,TH);  //W--E
  243.     (*EP)(line0,  line1+1,pixInRow-1,TH);  //NW--SE
  244.     (*EP)(line0+1,line1,  pixInRow-1,TH);  //NE--SW
  245.     (*EP)(line0,  line1,  pixInRow,TH);    //N--S
  246.  
  247. // Convert ColorSpec.values to Bitmap.bits:
  248.     Copy2Bitmap(line0,bits,bitRowBytes);
  249.  
  250. // Swap line0 with line1:
  251.     {ColorSpec* temp=line0;line0=line1;line1=temp;}
  252.     bits+=bitRowBytes;
  253.   }
  254.  
  255. // Convert the last row;
  256.   Copy2Bitmap(line0,bits,bitRowBytes);
  257.  
  258. // Release dynamic memory:
  259.   free(allocated);
  260. }
  261.  
  262. /***************** Local Functions ************************/
  263.  
  264. void Get1Line(
  265.     ColorSpec*    line,
  266.     void*         pix,
  267.     int         size,
  268.     ColorSpec*     CT,
  269.     int         pixelSize){
  270. int        i,r,g,b;
  271. unsigned long     x;
  272.   if (pixelSize==8) {
  273.     unsigned char*      PIX =((unsigned char*)pix);
  274.     for (i=0;i<size;i++) {
  275.       x=*PIX++;
  276.       line++;
  277.       *((double*)(line))=*((double*)(CT+x));
  278.       line->value=0;
  279.     }
  280.   } else if (pixelSize==16) {
  281.     unsigned short*     PIX =((unsigned short*)pix);
  282.     for (i=0;i<size;i++) {
  283.       x=*PIX++;
  284.       line++;
  285.       r=((x & 0x7C00) << 1)  | ((x & 0x7C00) >> 4) |
  286.     ((x & 0x7C00) >> 9)  | ((x & 0x7C00) >> 14);
  287.       g=((x & 0x03E0) << 6)  | ((x & 0x03E0) << 1) |
  288.     ((x & 0x03E0) >> 4)  | ((x & 0x03E0) >> 9);
  289.       b=((x & 0x001F) << 11) | ((x & 0x001F) << 6) |
  290.     ((x & 0x001F) << 1)  | ((x & 0x001F) >> 4);
  291.       line->value=0;
  292.       line->rgb.red=  (unsigned short)r;
  293.       line->rgb.green=(unsigned short)g;
  294.       line->rgb.blue= (unsigned short)b;
  295.     }
  296.   } else { //pixelSize not 8 or 16, so it must be 32
  297.     unsigned long*     PIX =((unsigned long*)pix);
  298.     for (i=0;i<size;i++) {
  299.       x=*PIX++;
  300.       line++;
  301.       r=((x & 0xFF0000) >> 8) | ((x & 0xFF0000) >> 16);
  302.       g= (x & 0x00FF00)       | ((x & 0x00FF00) >> 8);
  303.       b= (x & 0x0000FF)       | ((x & 0x0000FF) << 8);
  304.       line->value=0;
  305.       line->rgb.red=  (unsigned short)r;
  306.       line->rgb.green=(unsigned short)g;
  307.       line->rgb.blue= (unsigned short)b;
  308.     }
  309.   }
  310. }
  311.  
  312. void Copy2Bitmap(
  313.     ColorSpec*     P,
  314.     unsigned char*     bits,
  315.     int         size) {
  316. int         i;
  317.   P++;
  318.   for (i=0;i<size;i++) {
  319.     *bits = (unsigned char) (
  320.         (P[0].value & 0x80) |
  321.         (P[1].value & 0x40) |
  322.         (P[2].value & 0x20) |
  323.         (P[3].value & 0x10) |
  324.         (P[4].value & 0x08) |
  325.         (P[5].value & 0x04) |
  326.         (P[6].value & 0x02) |
  327.         (P[7].value & 0x01) );
  328.     P+=8;
  329.     bits++;
  330.   }
  331. }
  332.  
  333. void EdgeRedGreenBlue(
  334.     ColorSpec*     P,
  335.     ColorSpec*     Q,
  336.     int         size,
  337.     unsigned long     TH) {
  338. int         i;
  339. unsigned long     delta,acc;
  340.   for (i=0;i<size;i++) {
  341.     P++;Q++;
  342.     acc=(unsigned long)P->rgb.red-Q->rgb.red;
  343.     acc*=acc;
  344.     delta=(unsigned long)P->rgb.green-Q->rgb.green;
  345.     delta*=delta;
  346.     acc+=delta;
  347.     if (acc<delta) {P->value=Q->value=-1;continue;}
  348.     delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
  349.     delta*=delta;
  350.     acc+=delta;
  351.     if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  352.   }
  353. }
  354.  
  355. void EdgeGreenBlue(
  356.     ColorSpec*     P,
  357.     ColorSpec*     Q,
  358.     int         size,
  359.     unsigned long     TH) {
  360. int         i;
  361. unsigned long     delta,acc;
  362.   for (i=0;i<size;i++) {
  363.     P++;Q++;
  364.     acc=(unsigned long)P->rgb.green-Q->rgb.green;
  365.     acc*=acc;
  366.     delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
  367.     delta*=delta;
  368.     acc+=delta;
  369.     if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  370.   }
  371. }
  372.  
  373. void EdgeRedBlue(
  374.     ColorSpec*     P,
  375.     ColorSpec*     Q,
  376.     int         size,
  377.     unsigned long     TH) {
  378. int         i;
  379. unsigned long     delta,acc;
  380.   for (i=0;i<size;i++) {
  381.     P++;Q++;
  382.     acc=(unsigned long)P->rgb.red-Q->rgb.red;
  383.     acc*=acc;
  384.     delta=(unsigned long)P->rgb.blue-Q->rgb.blue;
  385.     delta*=delta;
  386.     acc+=delta;                                    
  387.     if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  388.   }
  389. }
  390.  
  391. void EdgeRedGreen(
  392.     ColorSpec*     P,
  393.     ColorSpec*     Q,
  394.     int         size,
  395.     unsigned long     TH) {
  396. int         i;
  397. unsigned long     delta,acc;
  398.    for (i=0;i<size;i++) {
  399.     P++;Q++;
  400.     acc=(unsigned long)P->rgb.red-Q->rgb.red;
  401.     acc*=acc;
  402.     delta=(unsigned long)P->rgb.green-Q->rgb.green;
  403.     delta*=delta;
  404.     acc+=delta;
  405.     if ((acc>=TH) || (acc<delta)) P->value=Q->value=-1;
  406.   }
  407. }
  408.  
  409. void EdgeBlue(
  410.     ColorSpec*     P,
  411.     ColorSpec*     Q,
  412.     int         size,
  413.     unsigned long     TH) {
  414. int         i;
  415. unsigned long     acc;
  416.   for (i=0;i<size;i++) {
  417.     P++;Q++;
  418.     acc=(unsigned long)P->rgb.blue-Q->rgb.blue;
  419.     acc*=acc;
  420.     if (acc>=TH) P->value=Q->value=-1;
  421.   }
  422. }
  423.  
  424. void EdgeGreen(
  425.     ColorSpec*     P,
  426.     ColorSpec*     Q,
  427.     int         size,
  428.     unsigned long     TH) {
  429. int         i;
  430. unsigned long     acc;
  431.   for (i=0;i<size;i++) {
  432.     P++;Q++;
  433.     acc=(unsigned long)P->rgb.green-Q->rgb.green;
  434.     acc*=acc;
  435.     if (acc>=TH) P->value=Q->value=-1;;
  436.   }
  437. }
  438.  
  439. void EdgeRed(
  440.     ColorSpec*     P,
  441.     ColorSpec*     Q,
  442.     int         size,
  443.     unsigned long     TH) {
  444. int         i;
  445. unsigned long     acc;
  446.   for (i=0;i<size;i++) {
  447.     P++;Q++;
  448.     acc=(unsigned long)P->rgb.red-Q->rgb.red;
  449.     acc*=acc;
  450.     if (acc>=TH) P->value=Q->value=-1;
  451.   }
  452. }
  453.